public class Main {
    public static void main(String[] args) {
        Solution1 s = new Solution1();
        System.out.println(s.longestValidParentheses("(()"));
        System.out.println(s.longestValidParentheses(")()())"));
        System.out.println(s.longestValidParentheses(""));
    }
}


//动态规划, 时间和空间复杂度O(n)
class Solution {
    int[] dp;

    public int longestValidParentheses(String s) {
        if(s.length() == 0){
            return 0;
        }
        dp = new int[s.length()];
        setDp(0, 0);
        int longest = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == ')'){
                if(i - getDp(i - 1) - 1 >= 0 && s.charAt(i - getDp(i - 1) - 1) == '('){
                    setDp(i, getDp(i - 1) + 2 + getDp(i - getDp(i - 1) - 2));
                    longest = Math.max(longest, getDp(i));
                }
            }
        }
        return longest;
    }

    int getDp(int i){
        if(i < 0){
            return 0;
        }
        return dp[i];
    }

    void setDp(int i, int v){
        dp[i] = v;
    }
}

//官方题解方法3，时间复杂度O(n), 空间复杂度O(1)
class Solution1 {
    int[] dp;

    public int longestValidParentheses(String s) {
        int count = 0;
        int lo = 0, hi;
        int longest = 0;
        //从左往右
        for(hi = 0; hi < s.length(); hi++){
            if(s.charAt(hi) == '('){
                count++;
            }
            else{
                count--;
                if(count == 0){
                    longest = Math.max(longest, hi - lo + 1);
                }
                else if(count < 0){
                    count = 0;
                    lo = hi + 1;
                }
            }
        }

        //从右往左
        count = 0;
        lo = s.length() - 1;
        for(hi = s.length() - 1; hi > -1; hi--){
            if(s.charAt(hi) == ')'){
                count++;
            }
            else{
                count--;
                if(count == 0){
                    longest = Math.max(longest, lo - hi + 1);
                }
                else if(count < 0){
                    count = 0;
                    lo = hi - 1;
                }
            }
        }
        return longest;
    }

}


//动态规划，复杂度太高
class Solution2 {
    public int longestValidParentheses(String s) {
        //dp: 左括号减右括号的个数，当值<0时，子序列不合法
        int[] dp = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                dp[i] = 1;
            }
            else{
                dp[i] = -1;
            }
        }

        int longest = 0;
        for(int w = 1; w < s.length(); w++){
            for(int i = 0; i + w < s.length(); i++){
                if(dp[i] < 0){
                    //子序列不合法
                    continue;
                }
                if(s.charAt(i + w) == '('){
                    dp[i]++;
                }
                else{
                    dp[i]--;
                    if(dp[i] == 0){
                        longest = Math.max(longest, w + 1);
                    }
                }
            }
        }

        return longest;
    }
}